package com.learn.finished;

import java.util.Arrays;

public class num_1818 {
    public static void main(String[] args) {
        int[] a ={1,2,3,4,5};
        int[] b ={1,2,3,4,5};
        System.out.println(Integer.MAX_VALUE);
    }
    public int oldMinAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int sum = 0, max = 0, mod = (int) 1e9 + 7;
        for (int i = 0; i < nums1.length; i++) {//两次循环看能每个元素最多能节省多少
            int N = nums2[i];
            int originAbs = Math.abs(nums1[i] - N);
            int minAbs = Integer.MAX_VALUE;
            for (int value : nums1) {
                minAbs = Math.min(minAbs, Math.abs(N - value));
            }
            max = Math.max(max, originAbs - minAbs);
            sum += originAbs;   //abs求和
        }
        return (sum - max) % mod;
    }
    /**
     * 二分法 优化暴力法内层循环使查找O(n)降到O(logn)
     * 1.复制num1,排序
     * 2.遍历num2, 使用二分查找最接近num2的两个元素计算最小绝对值差值.
     * O(nlogn)
     */
    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int[] sorted = nums1.clone();
        Arrays.sort(sorted);//排序num1复制
        int n = nums1.length;
        long sum = 0, max = 0, mod = (int) 1e9 + 7;//sum存总数 max存最大绝对值能省多少
        for (int i = 0; i < n; i++) {
            int n1 = nums1[i], n2 = nums2[i], originAbs = Math.abs(n1 - n2), minAbs = Integer.MAX_VALUE;
            //二分查找街接近n2的元素
            int left = 0, right = n - 1;
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (sorted[mid] >= n2) right = mid;
                else left = mid + 1;
            }
            //取与n2相近的左右最小的绝对值
            minAbs = Math.min(minAbs, Math.abs(n2 - sorted[right]));
            if (right - 1 >= 0) minAbs = Math.min(minAbs, Math.abs(n2 - sorted[right - 1]));
            max = Math.max(max, originAbs - minAbs);
            sum += originAbs;
        }
        return (int) ((sum - max) % mod);

    }
}
